//给你一个整数数组 arr ，以及 a、b 、c 三个整数。请你统计其中好三元组的数量。 
//
// 如果三元组 (arr[i], arr[j], arr[k]) 满足下列全部条件，则认为它是一个 好三元组 。 
//
// 
// 0 <= i < j < k < arr.length 
// |arr[i] - arr[j]| <= a 
// |arr[j] - arr[k]| <= b 
// |arr[i] - arr[k]| <= c 
// 
//
// 其中 |x| 表示 x 的绝对值。 
//
// 返回 好三元组的数量 。 
//
// 
//
// 示例 1： 
//
// 输入：arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
//输出：4
//解释：一共有 4 个好三元组：[(3,0,1), (3,0,1), (3,1,1), (0,1,1)] 。
// 
//
// 示例 2： 
//
// 输入：arr = [1,1,2,2,3], a = 0, b = 0, c = 1
//输出：0
//解释：不存在满足所有条件的三元组。
// 
//
// 
//
// 提示： 
//
// 
// 3 <= arr.length <= 100 
// 0 <= arr[i] <= 1000 
// 0 <= a, b, c <= 1000 
// 
//
// Related Topics 数组 枚举 👍 126 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2025-04-14 09:38:38
 * @description 1534.统计好三元组
 
 */
 
public class CountGoodTriplets {
    public static void main(String[] args) {
    //测试代码
    CountGoodTriplets fun = new CountGoodTriplets();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    //暴力枚举所有组合，复杂度高，
    public int countGoodTriplets1(int[] arr, int a, int b, int c) {
        int n = arr.length, cnt = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                for (int k = j + 1; k < n; ++k) {
                    if (Math.abs(arr[i] - arr[j]) <= a && Math.abs(arr[j] - arr[k]) <= b && Math.abs(arr[i] - arr[k]) <= c) {
                        ++cnt;
                    }
                }
            }
        }
        return cnt;
    }
    //统计 j-k<=b的二元组，然后找到满足i的约束条件
    //i的条件是  [i-j]<=a&&[i-k]<=c，  即i属于 [j-a,j+a]和[k-c,k+c]的交集
    //记为l,r，在统计二元组j,k时，只要知道i<j且满足在l,r区间的i的个数即可
    //为了一个i的频次数组前缀和，即可以o1得到l,r的个数
    public int countGoodTriplets(int[] arr, int a, int b, int c) {
        int res=0,n= arr.length;
        int [] sum=new int[1001];
        for (int j = 0; j < n; j++) {
            for (int k = j+1; k < n; k++) {
                //只统计符合条件的二元组
                if(Math.abs(arr[j]-arr[k])<=b){
                    int lj=arr[j]-a,rj=arr[j]+a;
                    int lk=arr[k]-c,rk=arr[k]+c;
                    int l=Math.max(0,Math.max(lj,lk)),r=Math.min(1000,Math.min(rj,rk));
                    if(l<=r){
                        if(l==0){
                            res+=sum[r];
                        }else {
                            res+=sum[r]-sum[l-1];
                        }
                    }
                }
            }
            //这段代码在每个j循环结束后执行，它的作用是：
            //将arr[j]到1000的所有sum数组元素值加1
            //这相当于在sum数组中记录所有≤k的元素的累计出现次数
            //本质上是在构建一个前缀和数组，其中sum[k]表示在j之前(即i的范围)有多少元素的值≤k
            for (int k = arr[j]; k <=1000; k++) {
                ++sum[k];
            }
        }
        return res;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
